package com.zhao.leetcode.bfs.medium;

/**
 * @program: arithmetic-do-exercise
 * @author: zhaohuan
 * @create: 2022-11-13 14:53
 * @description 地址：https://leetcode.cn/problems/word-search/description/?favorite=2cktkvj
 * 题目：单词搜索
 * 思路：BFS，需要记录是否扫描过
 **/
public class SearchWord {

    public static void main(String[] args) {
        SearchWord searchWord = new SearchWord();
        searchWord.exist(new char[][]{{'A','B','C','E'},{'S','F','E','S'},{'A','D','E','E'}}, "ABCESEEEFS");
    }

    public boolean exist(char[][] board, String word) {

        int x = board.length, y = board[0].length;

        boolean[][] bp;

        for (int i = 0; i < x; i++) {
            for (int j = 0; j < y; j++) {
                bp = new boolean[x][y];
                if (check(board, i, j, x - 1, y - 1, 0, word, bp)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean check(char[][] board, int i, int j, int x, int y, int start, String word, boolean[][] bp) {

        if (board[i][j] != word.charAt(start)) {
            return false;
        }
        start++;
        bp[i][j] = true;
        if (start == word.length()) {
            return true;
        }
        boolean flag = false;
        if (i < x && !bp[i + 1][j]) {
            flag |= check(board, i + 1, j, x, y, start, word, bp);
        }
        if (i > 0 && !bp[i - 1][j]) {
            flag |= check(board, i - 1, j, x, y, start, word, bp);
        }
        if (j < y && !bp[i][j + 1]) {
            flag |= check(board, i, j + 1, x, y, start, word, bp);
        }
        if (j > 0 && !bp[i][j - 1]) {
            flag |= check(board, i, j - 1, x, y, start, word, bp);
        }
        bp[i][j] = false;
        return flag;
    }


}
